package com.shindo.novie.class04;

/**
 * 两个单项链表相加问题
 * 给定两个链表的头节点head1 和 head2
 * 认为从左到右是某个数字从低位到高位，返回相加之后的链表
 * 例子  4->3->6     2->5->3
 * 返回：6->8->9
 * 解释：634 + 352 = 986
 * <p>
 * 测试连接：https://leetcode.com/problems/add-two-numbers/
 * <p>
 * 总结：
 * 注意划分情况：
 * 1、长链表 和 短短链 都有值
 * 2、短链表 为空，长链表有值
 * 3、长短链表都为空，要注意是否有进位，有进位需补充节点
 */
public class Code05_AddTwoNumbers {

    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 两数相加
     */
    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        int len1 = listLength(head1);
        int len2 = listLength(head2);
        ListNode l = len1 >= len2 ? head1 : head2;
        ListNode s = l == head1 ? head2 : head1;
        ListNode curL = l;
        ListNode curS = s;
        //记录最后一个不为空的元素，以便连接最高位进位生成的节点
        ListNode last = curL;
        //进位的值
        int carry = 0;
        //当前位数上各值相加的结果： 长链的值 + 短链的值 + 进位的值
        int curNum = 0;
        //短链有值，长链有值
        while (curS != null) {
            curNum = curL.val + curS.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
            curS = curS.next;
        }
        //短链无值，长链有值
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        //短链无值，长链无值，判断是否有进位情况
        if (carry != 0) {
            last.next = new ListNode(1);
        }
        return l;
    }

    //求链表长度
    public static int listLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(4, new ListNode(3, new ListNode(6)));
        ListNode head2 = new ListNode(2, new ListNode(5, new ListNode(3)));
        ListNode listNode = addTwoNumbers(head1, head2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
